'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-08-02 10:31:04
'''

'''
114. 二叉树展开为链表
给定一个二叉树，原地将它展开为一个单链表。

 

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

tips:采用栈，先压右节点，再压左键点，弹出节点后拼接。采用栈的先序遍历。
'''
from tree_node import *
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return None
        stack = [root]
        pre = None
        while stack:
            cur = stack.pop()
            if pre:
                pre.left=None
                pre.right=cur
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
            pre = cur
        return root

if __name__ == "__main__":
    null = 'null'
    root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
    for i,v in enumerate(root):
        root[i] = str(v)
    s = ','.join(root)
    # print(s)
    o_s = OfficialSerialize()
    root = o_s.deserialize(s)
    solution = Solution()
    solution.flatten(root)
    print(o_s.serialize(root))